package 暑假实习面试.阿里面试题;

public class Main {

    private int[][] arr;
    private int endX;
    private int endY;
    //上右下左
    private int[][] goArr={{-1,0},{0,1},{1,0},{0,-1}};
    private int result=Integer.MAX_VALUE;
    private int[][] dp;
    //已经走过的路
    boolean[][] haveGo;

    private int main(int[][] arr,int startX,int startY,int endX,int endY){
        this.arr=arr;
        this.haveGo=new boolean[arr.length][arr[0].length];
        dp=new int[arr.length][arr[0].length];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j]=Integer.MAX_VALUE;
            }
        }
        //对应数组下标都要进行减一
        this.endX=endX-1;
        this.endY=endY-1;
        dfs(startX-1,startY-1,0);
        return result==Integer.MAX_VALUE?-1:result;
    }

    //深度优先走下去
    private void dfs(int x,int y,int count) {

        if(dp[x][y]<=count){
            return;
        }

        if(x==endX&&y==endY){
            result=Math.min(result,count);
            return;
        }

        dp[x][y]=Math.min(dp[x][y],count);

        //开始四个方向走一走
        for (int i = 0; i < 4; i++) {

            boolean isOk=isOk(x+goArr[i][0],y+goArr[i][1],arr[x][y]);
            if(isOk){
                //符合规则才可以走下去
                haveGo[x+goArr[i][0]][y+goArr[i][1]]=true;
                dfs(x+goArr[i][0],y+goArr[i][1],count+1);
                haveGo[x+goArr[i][0]][y+goArr[i][1]]=false;
            }

        }

    }

    //下一步是否可以走?
    private boolean isOk(int nextX,int nextY,int thisNum){
        //是否越界
        if(nextX<0||nextX>=arr.length||nextY<0||nextY>=arr[0].length){
            return false;
        }

        //下一位的数字是否符合规则 && 没有走过
        return arr[nextX][nextY]>=thisNum&&!haveGo[nextX][nextY];

    }

    public static void main(String[] args) {
//        Scanner input=new Scanner(System.in);
//
//        int allLength=input.nextInt();
//        int itemLength=input.nextInt();
//
//        int startX=input.nextInt();
//        int startY=input.nextInt();
//        int endX=input.nextInt();
//        int endY=input.nextInt();
//
//        int[][] arr=new int[allLength][itemLength];
//
//        for (int i = 0; i < allLength; i++) {
//            for (int j = 0; j < itemLength; j++) {
//                arr[i][j]=input.nextInt();
//            }
//        }

        //测试数据

        int[][] arr2={{4,4,4},{4,4,4},{4,4,4},{4,4,6},{4,4,4}};
        int startX2=2;
        int startY2=3;
        int endX2=5;
        int endY2=3;

        //测试数据

        //开始书写解法
        Main main=new Main();
        int result = main.main(arr2, startX2, startY2, endX2, endY2);
//        int result = main.main(arr, startX, startY, endX, endY);
        System.out.println(result);

    }

}
